#include "common.h"

bool ans = false;
int arr[9][9];
int arr1[9][9];
int arr2[9][9];

void dfs(vector<vector<char>>& board, int x, int y)
{
	if (x >= 9)
	{
		ans = true;
		return;
	}
	if (board[x][y] == '.')
	{
		int n = (x / 3) * 3 + (y / 3);
		for (int i = 0; i < 9; i++)
		{
			if (arr1[x][i] == 0 && arr2[y][i] == 0 && arr[n][i] == 0)
			{
				arr1[x][i] = arr2[y][i] = arr[n][i] = 1;
				board[x][y] = '1' + i;
				if (x == 8 && y == 8)
				{
					ans = true;
					return;
				}
				if (y == 8)
					dfs(board, x + 1, 0);
				else
					dfs(board, x, y + 1);
				if (ans) return;
				board[x][y] = '.';
				arr1[x][i] = arr2[y][i] = arr[n][i] = 0;
			}
		}
	}
	else
	{
		if (x == 8 && y == 8)
		{
			ans = true;
			return;
		}
		if (y == 8)
			dfs(board, x + 1, 0);
		else
			dfs(board, x, y + 1);
	}
}

void solveSudoku(vector<vector<char>>& board)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] != '.')
			{
				int num = board[i][j] - '1';
				int n = (i / 3) * 3 + (j / 3);
				if (arr1[i][num] == 0 && arr2[j][num] == 0 && arr[n][num] == 0)
				{
					arr1[i][board[i][j] - '1'] = 1;
					arr2[j][board[i][j] - '1'] = 1;
					arr[n][board[i][j] - '1'] = 1;
				}
			}
		}
	}
	dfs(board, 0, 0);
}